package com.kavinz.algo.string.other;

/**
 * 
 * 《Cracking the coding interview》- #Interview Questions 
 * 1.3 Design an algorithm
 * and write code to remove the duplicate characters in a string without using
 * any additional buffer NOTE: One or two additional variables are fine An extra
 * copy of the array is not FOLLOW UP Write the test cases for this method
 * 
 * @author Kevin Zhao
 * 
 */
public class Deduplicator {

	public static String deduplicate(String input) {
		if (input == null)
			return null;
		int[] registry = new int[256];
		char[] inputCharArray = input.toCharArray();

		for (int i = 0; i < input.length(); i++) {
			// no duplication
			if (registry[(int) input.charAt(i)] == 0)
				registry[(int) input.charAt(i)]++;
			// found duplication and mark it with a special value
			else
				inputCharArray[i] = Character.MAX_VALUE;
		}

		// po
		StringBuilder result = new StringBuilder();
		for (char character : inputCharArray) {
			// copy the character with no special mark
			if (character != Character.MAX_VALUE)
				result.append(character);
		}

		return result.toString();
	}

	public static void main(String[] args) {
		System.out.println(Deduplicator.deduplicate("aacgdedg"));
		System.out.println(Deduplicator.deduplicate("aaaaaaa"));
		System.out.println(Deduplicator.deduplicate("aaabbbcccddd"));
		System.out.println(Deduplicator.deduplicate(null));
		System.out.println(Deduplicator.deduplicate("2sa09gas"));
		System.out.println(Deduplicator.deduplicate("33998fyri3p"));
		System.out.println(Deduplicator.deduplicate("1349anva;lnv203haos"));
		System.out.println(Deduplicator
				.deduplicate("2g3qvapuosfq0hperabonvdq9p34g0qew"));
	}
}
